import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * <p>
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode mid = head;
        ListNode cur = head;

        if (Objects.isNull(cur.next)) {
            return mid;
        }
        cur = cur.next;
        mid = mid.next;

        while (Objects.nonNull(cur.next)) {
            cur = cur.next;
            if (Objects.isNull(cur.next)) {
                return mid;
            }
            cur = cur.next;
            mid = mid.next;
        }

        return mid;
    }

}